|
In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs ("cliques") in a graph, i.e., sets of elements where each pair of elements is connected. For example, the maximum clique problem arises in the following real-world setting. Consider a social network, where the graph’s vertices represent people, and the graph’s edges represent mutual acquaintance. To find a largest subset of people who all know each other, one can systematically inspect all subsets, a process that is too time-consuming to be practical for social networks comprising more than a few dozen people. Although this brute-force search can be improved by more efficient algorithms, all of these algorithms take exponential time to solve the problem. Therefore, much of the theory about the clique problem is devoted to identifying special types of graph that admit more efficient algorithms, or to establishing the computational difficulty of the general problem in various models of computation.〔 Along with its applications in social networks, the clique problem also has many applications in bioinformatics and computational chemistry.〔For more details and references, see clique (graph theory).〕 Clique problems include: *finding a maximum clique (largest clique by vertices), *finding a maximum weight clique in a weighted graph, *listing all maximal cliques (cliques that cannot be enlarged) *solving the decision problem of testing whether a graph contains a clique larger than a given size. These problems are all hard: the clique decision problem is NP-complete (one of Karp's 21 NP-complete problems), the problem of finding the maximum clique is both fixed-parameter intractable and hard to approximate, and listing all maximal cliques may require exponential time as there exist graphs with exponentially many maximal cliques. Nevertheless, there are algorithms for these problems that run in exponential time or that handle certain more specialized input graphs in polynomial time.〔For surveys of these algorithms, and basic definitions used in this article, see and .〕 ==History== Although complete subgraphs have been studied for longer in mathematics,〔Complete subgraphs make an early appearance in the mathematical literature in the graph-theoretic reformulation of Ramsey theory by .〕 the term "clique" and the problem of algorithmically listing cliques both come from the social sciences, where complete subgraphs are used to model social cliques, groups of people who all know each other. The "clique" terminology comes from , and the first algorithm for solving the clique problem is that of ,〔 who were motivated by the sociological application. Since the work of Harary and Ross, many others have devised algorithms for various versions of the clique problem.〔 In the 1970s, researchers began studying these algorithms from the point of view of worst-case analysis; see, for instance, , an early work on the worst-case complexity of the maximum clique problem. Also in the 1970s, beginning with the work of and , researchers began finding mathematical justification for the perceived difficulty of the clique problem in the theory of NP-completeness and related intractability results. In the 1990s, a breakthrough series of papers beginning with and reported at the time in major newspapers,〔 showed that it is not even possible to approximate the problem accurately and efficiently. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Clique problem」の詳細全文を読む スポンサード リンク
|